Packet forwarding devices, such as layer 3 or IP routers, typically use one or more tables to store packet forwarding information. For example, layer 3 packet forwarding devices may include a hardware-implemented layer 3 host table that typically stores entries corresponding to hosts that are directly connected to the packet forwarding device. Each entry may include an IP address of a locally connected host and corresponding forwarding information for the locally connected host. When a packet arrives at the packet forwarding device, a lookup may be performed in the layer 3 host table based on the destination IP address in the packet. If a matching entry is located, the corresponding packet forwarding information is extracted from the layer 3 host table and used to forward the packet to the destination host. If an entry is not located, a miss occurs, and a slower lookup is performed using software.
Another type of table that may be maintained in a layer 3 packet forwarding device is a longest prefix matching (LPM) table. Each entry in a longest prefix matching table may include a subnet address and a subnet mask to be applied to destination IP addresses of incoming packets. When a packet is received, the subnet mask for each entry in the LPM table is applied to the destination IP address of the packet, and the masked address searched in the table. The entry with the longest prefix that matches the masked address in the received packet is used to extract next hop address information for the packet. Using an LPM table allows remote hosts to be identified by next hops without requiring entries in the LPM table for each individual remote host.
One problem with conventional packet forwarding devices is that space for the LPM and host tables is limited. For example, both tables are typically implemented in hardware to increase the number of hosts covered by hardware forwarding and therefore packet forwarding lookup speed. LPM tables are typically populated based on participation in routing protocols, such as routing information protocol (RIP), border gateway protocol (BGP) or open shortest path first (OSPF). When an LPM table becomes full, entries for remote hosts can be placed in the host table. However, the host table can also become full. When this occurs, packets received for destinations that are not present in the LPM or host tables must be forwarded using software, which results in longer lookup times.
In order to increase the routing efficiency of a layer 3 packet forwarding device, older entries in LPM and host tables may be replaced with newer entries. Conventionally, the replacement criteria for an entry include a least recently used (LRU) algorithm. That is, a host table entry that was used least recently may be replaced with a new entry for which a packet forwarding lookup fails. One problem with using an LRU algorithm to replace host table entries is that it is based on individual packets, which may result in excessive replacement of entries in the host table. For example, each time a miss occurs, an entry in the host table may be replaced. Such excessive replacement is undesired because replacing entries in the host table may be a processor intensive operation that requires a software copy of the host table be copied to hardware.
Another problem associated with using an LRU algorithm to replace entries in the host table is that such an algorithm does not take into account the volume of packets addressed to a destination. For example, an entry that was used 1000 times during a time interval more than one minute ago may be replaced by an entry that was used only once in the last minute. The high-volume entry may be more likely to be utilized in the future with a high volume than the low-volume entry. Thus, if the high-volume entry is replaced by the low-volume entry, multiple misses may occur before the high-volume entry can be re-added to the host table.
Accordingly, in light of these difficulties associated with conventional layer 3 packet forwarding devices, there exists a need for methods, systems, and computer program products for controlling updating of a layer 3 host table based on packet forwarding miss counts.
Again, packet forwarding devices, such as layer 3 or Internet protocol (IP) routers, typically use one or more tables to store packet forwarding information. Typically, packet forwarding devices include one or more hardware-implemented tables in addition to software-implemented tables in order to reduce packet forwarding information lookup time. For example, layer 3 packet forwarding devices may include a hardware-implemented host table populated with entries corresponding to individual hosts. When a packet arrives at a layer 3 packet forwarding device, a lookup may first be performed in the hardware host table. If the lookup is successful, the packet may be forwarded to a host corresponding to the matching entry in the table. If the lookup in the hardware host table fails to locate a match, a lookup may be performed in a longest prefix matching (LPM) table to locate the entry with the longest prefix that matches the address in the received packet. If the lookup in the LPM table fails to locate a longest prefix match, a software routing table may be searched in order to successfully forward the packet.
In some implementations, a hardware-implemented host table stores entries corresponding to hosts directly connected to the packet forwarding device. Each entry in the host table may include an IP address of a locally connected host and corresponding forwarding information. When a layer 3 packet arrives at the packet forwarding device, a lookup may be performed in the host table based on the destination IP address in the packet. This lookup is typically performed using a hashing function that identifies matching entries using a search key. If a matching entry is located, the corresponding packet forwarding information is extracted from the host table and used to forward the packet to the destination host. Host tables are typically searched before other tables because they store the most specific forwarding information for layer 3 packets.
A hardware-implemented LPM table stores subnet addresses and subnet masks to be applied to destination IP addresses of incoming packets. When a layer 3 packet is received, logical steps may be performed by a packet forwarding device where the subnet mask for each entry in the LPM table is applied to the destination IP address of the packet, and the masked address is searched in the table. In some implementations, these steps may be performed in a single LPM lookup using a special data structure, such as a Radix tree. The entry with the longest prefix that matches the masked address in the received packet is used to extract next hop address information for the packet. The next hop address typically corresponds to the next hop or machine in a path through which a remote host corresponding to the destination IP address in the packet is reachable. Using an LPM table allows remote hosts to be identified by next hops without requiring entries in the LPM table for each individual remote host. Thus, LPM tables may reduce a large number of hosts into fewer route entries by combining entries with the same next hop information. This allows an LPM table to store matching entries for more hosts than a host table of the same size.
Software lookups are performed by searching a much larger software table that stores layer 3 packet forwarding information. Lookups performed in software are significantly slower than lookups performed in hardware and therefore, it is desirable to perform as few lookups in software as possible.
As stated above, both host and LPM tables may be implemented or stored in hardware of a layer 3 packet forwarding device. In some implementations, the memory space available for both tables is shared. In order to increase the routing efficiency of conventional layer 3 packet forwarding devices, the relative sizes of the host and LPM tables are based on the expected number of communicating IP hosts. For example, edge devices that connect to a small number of hosts may utilize more memory for the host table and less for the LPM table. Devices, referred to as aggregators, that serve many communicating IP hosts may utilize more memory for the LPM table and less for the host table. Aggregators typically connect numerous smaller devices to a network infrastructure backbone or core network device and therefore route packets for a large number of hosts.
In edge devices, it may be desirable to route packets primarily using a host table, since the size of the host table would be small. In aggregators, it may be desirable to route packets primarily using an LPM table, since its entries represent plural hosts and populating a host table with all possible hosts would result in a table size that exceeds available memory space.
Layer 3 packet forwarding devices may have multiple modules, each containing host and LPM tables, for forwarding layer 3 packets. Conventionally, these modules are programmed identically and contain identical host and LPM tables as described above. However, as described above, it may be desirable to route some packets primarily using a host table and others primarily using an LPM table. Conventional IP packet forwarding devices do not provide for such varied operation.
Accordingly, there exists a need for improved methods, systems, and computer program products for routing layer 3 packets.